
# 希尔排序
def shell_sort(lst):
    n = len(lst)
    gap = n//2
    while gap > 0:
        for i in range(gap,n):
            for j in range(i,gap-1,-gap):
                if lst[j] < lst[j-gap]:
                    lst[j],lst[j-gap] = lst[j-gap],lst[j]
                else:
                    break
        gap //=2
    return lst

'''
平均复杂度：O(n*logN) , 最好：O(n*logN^2) ,最坏： O(n*logN^2)
空间复杂度：O(1)

'''

print(shell_sort([5,4,3,2,1]))

